


Road Trip

by pozorvlak



Category: The Avengers (Marvel Movies), The Avengers (Marvel) - All Media Types
Genre: Dubious Science, Gen, Mathematics, NP-completeness, Tony Stark can use the term "exponential" correctly
Language: English
Status: Completed
Published: 2016-06-09
Updated: 2016-06-09
Packaged: 2018-07-14 02:15:07
Rating: General Audiences
Warnings: No Archive Warnings Apply
Chapters: 1
Words: 420
Publisher: archiveofourown.org
Story URL: https://archiveofourown.org/works/7148246
Author URL: https://archiveofourown.org/users/pozorvlak/pseuds/pozorvlak
Summary: <blockquote class="userstuff">
              <p>The Avengers do battle with a classic problem from theoretical computer science.</p>
            </blockquote>





	Road Trip

**Author's Note:**

  * For [elmyra](https://archiveofourown.org/users/elmyra/gifts).



> This is [elmyra's fault](https://twitter.com/elmyra/status/740861275211767808).

“You may have found the locations of my dirty bombs, but they’re spread right across the continent, in hundreds of cities. You’ll never get to them all in time. AHAHAHAHAHAHA!!!!!”

Tony cut the call.

“OK, people, let’s work the problem. Assuming five minutes to find and deactivate each bomb once we’re in its rough location, travelling at Mach 2 and ignoring acceleration time… lessee, the continental US is 2700 miles wide and 1600 miles high, we could split into teams and… yeah, I think we can just do this before the bombs go off, but we’ll have to be _very_ efficient.”  
“Fine, so ask F.R.I.D.A.Y. to calculate optimal routes and let’s go!”  
“There’s a problem with that, Steve. Do you know what a Turing Machine is?”  
“Named after Alan Turing? We used to go running together, but he never talked about his work.”  
“…of course you did. Anyway, Turing machines - like F.R.I.D.A.Y. - have certain fundamental limitations. Some things they can’t do at all - your old running buddy proved that in grad school - and some things they can do, but not efficiently.”  
“And this is one of them?”  
“Yep. Given a list of cities and the distances between them, find a path shorter than X that visits them all. Every time you add a city, the problem gets twice as hard. A hundred cities? Sure, no problem. A hundred and ten? Get a cup of coffee. A hundred and twenty? Several days. Two hundred? Forget it. The universe will end before you’ve finished calculating.”  
"You've got whole floors full of computers in this building, what if you used them all?"  
"That only gets us a linear speedup, and we're fighting exponential growth."  
“There must be something we can do, Tony!”  
“Well, I suppose NP-completeness is about the hardest _instances_ of the problem, and some of those will be pathological, so we might get lucky and find a solution quickly. Or maybe we can use a heuristic approach and hope we find something good enough - dammit, I miss Bruce…”

The door blew open with a rush of wind, and Pietro blurred to a halt.

“Four hundred and thirty seven bombs defused - bomb in Milwaukee was dud. Think I got them all. Went to closest unvisited city each time, had to make long detour back to Nashville.”

Tony pinched the bridge of his nose.

“Or we could use a simple greedy algorithm and run really really fast. Yeah. I guess that might work.”


End file.
